package algorithm.dynamic_programming;

public class LeetCode70_ClimbStairs {

    public static long dynamic1(int n) {
        //初始化数组
        long[] dp = new long[n + 1];
        //阶梯n为1 有一种走法
        dp[1] = 1;
        //阶梯n为2 有两种走法
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            //当阶梯为n时，因为每次只能爬1或者2级阶梯，所以有a[i-1] + a[i-2]种走法
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static long dynamic2(int n) {
        long prev = 1, cur = 1, next;
        for(int i = 0; i < n - 1; i++){
            next = prev + cur;
            prev = cur;
            cur = next;
        }
        return cur;
    }
}
